/**
 * 图数据结构的实现类，用于存储和操作图形结构。
 */
package com.logic.comment.util;

import com.comment.exception.ServiceException;

import java.util.*;

public class Graph {
    /**
     * 使用邻接表表示图，键为节点，值为与键相邻的节点集合。
     * 使用Set可以自动去重。
     */
    private final Map<Integer, Set<Integer>> adjList;

    /**
     * 构造一个空图。
     */
    public Graph() {
        adjList = new HashMap<>();
    }

    /**
     * 添加一条单向边。
     *
     * @param source 边的起始节点
     * @param target 边的目标节点
     */
    public void oneWayAddEdge(Integer source, Integer target) {
        adjList.computeIfAbsent(source, k -> new HashSet<>()).add(target);
    }

    /**
     * 添加一条双向边。
     *
     * @param source 边的起始节点
     * @param target 边的目标节点
     */
    public void twoWayAddEdge(Integer source, Integer target) {
        adjList.computeIfAbsent(source, k -> new HashSet<>()).add(target);
        adjList.computeIfAbsent(target, k -> new HashSet<>()).add(source);
    }

    /**
     * 使用广度优先搜索找到图中所有从起始节点到结束节点的路径。
     *
     * @param start 起始节点
     * @param end   结束节点
     * @return 所有路径的集合
     */
    public Set<Set<Node>> bfsAllPaths(Integer start, Integer end) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        Map<Integer, Integer> parent = new HashMap<>();
        Set<Set<Node>> lists = new LinkedHashSet<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            // 遍历当前节点相邻的所有节点，判断是否已访问过，以确定是否记录路径或加入队列
            for (int neighbor : adjList.getOrDefault(current, Collections.emptySet())) {
                if (neighbor == end) {
                    parent.put(neighbor, current);
                    List<Integer> path = new ArrayList<>();
                    for (int step = end; step != start; step = parent.get(step)) {
                        path.add(step);
                    }
                    path.add(start);
                    Collections.reverse(path);
                    Set<Node> set = new HashSet<>();
                    for (int i = 0; i < path.size() - 1; i++) {
                        Node node = new Node();
                        node.setA(path.get(i));
                        node.setB(path.get(i + 1));
                        set.add(node);
                    }
                    lists.add(set);
                } else if (!parent.containsKey(neighbor)) {
                    queue.add(neighbor);
                    parent.put(neighbor, current);
                }
            }
        }
        return lists;
    }

    /**
     * 使用广度优先搜索找到图中所有从起始节点到结束节点的路径。
     *
     * @param start 起始节点
     * @param end   结束节点
     * @return 所有路径的集合
     */
    public Set<Set<Node>> bfsAllPaths(Integer start, Integer end , Map<String, Integer> cosMap) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        Map<Integer, Integer> parent = new HashMap<>();
        Set<Set<Node>> lists = new LinkedHashSet<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            // 遍历当前节点相邻的所有节点，判断是否已访问过，以确定是否记录路径或加入队列
            for (int neighbor : adjList.getOrDefault(current, Collections.emptySet())) {
                if (neighbor == end) {
                    parent.put(neighbor, current);
                    List<Integer> path = new ArrayList<>();
                    for (int step = end; step != start; step = parent.get(step)) {
                        path.add(step);
                    }
                    path.add(start);
                    Collections.reverse(path);
                    Set<Node> set = new HashSet<>();
                    for (int i = 0; i < path.size() - 1; i++) {
                        Node node = new Node();
                        node.setA(path.get(i));
                        node.setB(path.get(i + 1));
                        Integer cos = cosMap.getOrDefault(node.getKey(),0);
                        node.setCos(cos);
                        set.add(node);
                    }
                    lists.add(set);
                } else if (!parent.containsKey(neighbor)) {
                    queue.add(neighbor);
                    parent.put(neighbor, current);
                }
            }
        }
        return lists;
    }

    /**
     * 使用广度优先搜索找到图中从起始节点到结束节点的最短路径。
     *
     * @param start 起始节点
     * @param end   结束节点
     * @return 最短路径
     * @throws ServiceException 如果没有可用路径
     */
    public List<Node> bfsMinPaths(Integer start, Integer end) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == end) {
                List<Integer> path = new ArrayList<>();
                for (int step = end; step != start; step = parent.get(step)) {
                    path.add(step);
                }
                path.add(start);
                Collections.reverse(path);

                List<Node> list = new ArrayList<>();
                for (int i = 0; i < path.size() - 1; i++) {
                    Node node = new Node();
                    node.setA(path.get(i));
                    node.setB(path.get(i + 1));
                    list.add(node);
                }
                return list;
            }
            for (int neighbor : adjList.getOrDefault(current, Collections.emptySet())) {
                if (!parent.containsKey(neighbor)) {
                    parent.put(neighbor, current);
                    queue.add(neighbor);
                }
            }
        }
        throw new ServiceException("无可用路径");
    }
}
